//https://leetcode.cn/problems/maximum-area-of-a-piece-of-cake-after-horizontal-and-vertical-cuts/?envType=daily-question&envId=2023-10-27

class Solution {
public:
    int maxArea(int h, int w, vector<int>& horizontalCuts, vector<int>& verticalCuts) {
        sort(horizontalCuts.begin(), horizontalCuts.end());
        sort(verticalCuts.begin(), verticalCuts.end());
        
        int maxx = max(horizontalCuts[0], h - horizontalCuts.back());
        int maxy = max(verticalCuts[0], w - verticalCuts.back());
        
        for (int i = 1; i < horizontalCuts.size(); i++) {
            maxx = max(maxx, horizontalCuts[i] - horizontalCuts[i-1]);
        }
        
        for (int i = 1; i < verticalCuts.size(); i++) {
            maxy = max(maxy, verticalCuts[i] - verticalCuts[i-1]);
        }
        
        long long maxS = (long long)maxx * maxy;
        int mod = (int)1e9 + 7;
        return maxS % mod;
    }
};
